package com.SuanFa.mayukun;


import java.util.Arrays;

/**
 * 快速排序
 */
public class kuaisupaixu {
    public static void main(String[] args) {
        int[] nums = {8,3,5,7,6,4,9,2};
        quickSort(nums,0,nums.length-1);
        System.out.println(Arrays.toString(nums));
    }
    public static void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(nums, left, right);
            quickSort(nums, left, pivotIndex - 1);
            quickSort(nums, pivotIndex + 1, right);
        }
    }

    private static int partition(int[] nums, int left, int right) {
        int base = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= base) {
                right--;
            }
            if (left < right) {
                nums[left] = nums[right];
                left++;
            }
            while (left < right && nums[left] < base) {
                left++;
            }
            if (left < right) {
                nums[right] = nums[left];
                right--;
            }
            nums[left] = base;
        }
        return left;
    }

}
